/*
对于一个无序数组，求排序完成后的相邻元素的最大差值，要求时间复杂度O(1)
 */

function maxGap (arr) {
  if (arr === null || arr.length < 2) {
    return 0
  }
  const max = Math.max(...arr)
  const min = Math.min(...arr)
  if (max === min) {
    return 0
  }
  const arrLen = arr.length
  const buckCounts = arrLen + 1

  // 模拟桶，包含桶中是否有元素，最大值最小值信息
  const hasNum = new Array(buckCounts)
  const maxNum = new Array(buckCounts)
  const minNum = new Array(buckCounts)

  for (let i = 0; i < arrLen; i++) {
    const bid = buckIndex(arr[i], arrLen, min, max)
    maxNum[bid] = hasNum[bid] ? Math.max(maxNum[bid], arr[i]) : arr[i]
    minNum[bid] = hasNum[bid] ? Math.min(maxNum[bid], arr[i]) : arr[i]
    hasNum[bid] = true
  }

  let res = 0
  let lastMax = maxNum[0]
  for (let i = 1; i < buckCounts; i++) {
    if (hasNum[i]) {
      res = Math.max(minNum[i] - lastMax, res)
      lastMax = maxNum[i]
    }
  }
  return res
}

function buckIndex (num, arrLen, min, max) {
  return Math.floor((num - min) / ((max - min) / arrLen))
}

const arr1 = [10, 6, 3, 1, 0, 7, 4]
console.log(maxGap(arr1))
